#include "my_algorithm.h"

int k1, k2;
int *ans1;
int **ans2;
int *colsize;


int *right_order;  // 安装顺序
int **adj_table;   // 依赖关系的邻接表

// 找出仪器依赖条件的顺序
int* find_order(int numInstruments, int **prerequisites, int prerequisitesSize)
{
    int *ret = (int *)malloc(numInstruments*sizeof(int));
    int queue[1005] = {0};
    int right_idx = 0, left_idx = 0;
    for (int i = 0; i < prerequisitesSize; i++) {
        queue[prerequisites[i][2]]++;
    }
    for (int i = 0; i < numInstruments; i++) {
        if (queue[i] == 0) {
            ret[right_idx++] = i;
        }
    }
    while (left_idx < right_idx) {
        int k = ret[left_idx++];
        for (int i = 0; i < prerequisitesSize; i++) {
            if (prerequisites[i][1] == k) {
                if (--queue[prerequisites[i][2]] == 0) {
                    ret[right_idx++] = prerequisites[i][2];
                }
            }
        }
    }
    return ret;
}

void create_adj_table(){
    adj_table = (int**)malloc(n_instrument*sizeof(int*));
    for (int i = 0; i < n_instrument; ++i) {
        adj_table[i] = (int*)malloc(n_instrument*sizeof(int));
        for (int j = 0; j < n_instrument; ++j) {
            adj_table[i][j] = -1;  // 邻接表初始值为-1
        }
    }
    for (int i = 0; i < E; ++i) {
        int t = Graph[i][0], v1 = Graph[i][1], v2 = Graph[i][2];
        adj_table[v1][v2] = t;  //  依赖为0，协同为1
    }
}

int get_right(int id)
{
    int end = n_window-1;
    for (int i = 0; i < n_instrument; ++i) {
        if (adj_table[id][i] == 1) {  // 协同
            end = end <= (instrument_arr[i]->w) ? end : (instrument_arr[i]->w);
        } else if (adj_table[id][i] == 0) {  // 依赖
            end = end < (instrument_arr[i]->w) ? end : (instrument_arr[i]->w - 1);
        }
    }
    return end;
}

int get_window(int id)
{
    int idx = 0;
    for (int i = 0; i < n_instrument; ++i) {
        int v = adj_table[i][id];
        if (v == -1) continue;
        if (!instrument_arr[i]->fixed){
            puts("ERROR: before inst is not fixed.");
            exit(0);
        }
        int pre_idx = instrument_arr[i]->w;
        if (v == 0) {  // 依赖
            idx = (idx > pre_idx) ? idx : (pre_idx+1);
        } else if (v == 1) {  // 协同
            idx = (idx >= pre_idx) ? idx : pre_idx;
        }
    }
    return idx;
}

int get_window_area(int id, int start, int *a_idx, int *real_cost)
{
    int idx = start;

    int t = instrument_arr[id]->t;  // 仪器类型
    while (true) {
        if (idx >= n_window) {
            *real_cost = INT_MAX;
            break;
            puts("Error:Array Index Overflow.");
            exit(0);
        }

        // 窗口匹配-预加工
        if (instrument_arr[id]->main && !window_arr[idx]->prework[t]) {
            idx ++;
            continue;
        }
        // 车间区域匹配-能源
        bool matched = false;
        int cost = INT_MAX;
        for (int i = 0; i < window_arr[idx]->r->ka; ++i) {
            struct area* tmp = window_arr[idx]->r->a[i];
            int e = tmp->energy_type;  // 区域能源类型
            if ((t == 0 && e == 0) || (t == 0 && e == 1)
                || (t == 1 && e == 0) || (t == 1 && e == 2)
                || (t == 2 && e == 3) || (t == 2 && e == 4)){
                int cost2 = Instrument_information[id][e+1];
                if (cost2 < cost){
                    *a_idx = tmp->i;
                    cost = cost2;
                    matched = true;
                }
            }
        }
        *real_cost = cost;
        if (matched) break;
        idx++;
    }
    return idx;
}

void install(int id, int w, int a)
{
    instrument_arr[id]->w = w;
    instrument_arr[id]->w2 = window_arr[w]->i;
    instrument_arr[id]->a = a;
    instrument_arr[id]->fixed = true;
}

void first_plan()
{
    // 构建依赖关系的邻接表
    create_adj_table();
    // 获取依赖的正确次序
    right_order = find_order(n_instrument, Graph, E);

    // 按照次序从左往右依次安装
    for (int i = 0; i < n_instrument; ++i) {
        int id = right_order[i];
        // 寻找安装窗口和区域
        int idx1 = get_window(id);
        int a_idx, real_cost;
        int idx2 = get_window_area(id, idx1, &a_idx, &real_cost);
        // 安装
        install(id, idx2, a_idx);
    }
}

void second_plan()
{
    for (int i = n_instrument-1; i >= 0; --i) {
        int id = right_order[i];
        int start = instrument_arr[id]->w, end = get_right(id);
        int window = instrument_arr[id]->w, area = instrument_arr[id]->a;

        int old_cost, new_cost;
        get_window_area(id, start, &area, &old_cost);
        for (int j = start; j <= end; ++j) {
            int old_window = window, old_area = area;

            int w = get_window_area(id, j, &area, &new_cost);

            if (w > end || new_cost == INT_MAX) {
                window = old_window;
                area = old_area;
                break;
            }
            if (new_cost < old_cost) {
                old_cost = new_cost;
                window = w;
            } else {
                window = old_window;
                area = old_area;
            }
        }
        // 安装
        install(id, window, area);
    }
}

void get_answer()
{
    // 规划算法
    first_plan();
    second_plan();
    // 提取答案
    k1 = n_instrument;
    ans1 = (int*) malloc(k1*sizeof(int));
    for (int i = 0; i < k1; ++i) {
        ans1[i] = instrument_arr[i]->a;
    }
    k2 = T;
    ans2 = (int**) malloc(T*sizeof(int*));
    colsize = (int*)malloc(T*sizeof(int));
    for (int i = 0; i < T; ++i) {
        colsize[i] = 2 + F[i];
        ans2[i] = (int*)malloc(colsize[i]*sizeof(int));
        ans2[i][0] = F[i]+1;
        for (int j = 0; j < F[i]+1; ++j) {
            ans2[i][1+j] = instrument_arr[main_stream[i][j]]->w2;
        }
    }
}
